;; e1.20

(define (gcd a b)
    (if (= b 0)
        a
        (gcd b (remainder a b))))

;;; applicative order evaluation

(display "applicative order eval\n")

(gcd 20 40)
; -> definition expansion
(if (= 40 0)
    20
    (gcd 40 (remainder 20 40)))
; -> remainder reduction
(if (= 40 0)
    20
    (gcd 40 20))
; -> if evaluation
(gcd 40 20)
; -> definition expansion
(if (= 20 0)
    40
    (gcd 20 (remainder 40 20)))
; -> remainder reduction
(if (= 20 0)
    40
    (gcd 20 0))
; -> if evaluation
(gcd 20 0)
; -> definition expansion
(if (= 0 0)
    20
    (gcd 0 (remainder 20 0)))
; -> remainder reduction
(if (= 0 0)
    20
    (gcd 0 20))
; -> if evaluation
20

; => total 3 remainder reductions

;;; normal order evaluation

(display "normal order eval\n")

(gcd 20 40)
; -> definition expansion
(if (= 40 0)
    20
    (gcd 40 (remainder 20 40)))
; -> if evaluation
(gcd 40 (remainder 20 40))
; -> definition expansion
(if (= (remainder 20 40) 0)
    40
    (gcd (remainder 20 40) (remainder 40 (remainder 20 40))))
; -> remainder reduction
(if (= 20 0)
    40
    (gcd (remainder 20 40) (remainder 40 (remainder 20 40))))
; -> if evaluation
(gcd
    (remainder 20 40)
    (remainder 40 (remainder 20 40)))
; -> definition expansion
(if (= (remainder 40 (remainder 20 40)) 0)
    (remainder 20 40)
    (gcd
        (remainder 40 (remainder 20 40))
        (remainder
            (remainder 20 40)
            (remainder 40 (remainder 20 40)))))
; -> remainder reduction x2
(if (= 0 0)
    (remainder 20 40)
    (gcd
        (remainder 40 (remainder 20 40))
        (remainder
            (remainder 20 40)
            (remainder 40 (remainder 20 40)))))
; -> if evaluation
(remainder 20 40)
; -> remainder reduction
20

; => total 4 remainder reductions
#| if gcd takes k steps, normal order eval takes k-2 remainder evaluations after final if evaluation alone |#
